package com.lollipop.programming.sort;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @Author Lollipop
 * @Date 2025/4/7 14:25
 * @Description 快速排序V2
 */
@Slf4j
public class QuickSortV2 {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1};
        log.info("排序前：{}", Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        log.info("排序后：{}", Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点 选择基准（Pivot）：从数组中选择一个元素作为基准（通常选择第一个、最后一个或随机元素）
            int pivotIndex = partition(arr, low, high);
            // 递归排序左子数组
            quickSort(arr, low, pivotIndex - 1);
            // 递归排序右子数组
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 随机选择基准
    private static int randomizedPartition(int[] arr, int low, int high) {
        // 随机选择基准并交换到首位
        int randomIndex = low + (int) (Math.random() * (high - low + 1));
        swap(arr, randomIndex, low);
        return partition(arr, low, high);
    }

    /**
     * 分区（Partition）：
     * 将比基准小的元素移到基准的左侧。
     * 将比基准大的元素移到基准的右侧。
     * 基准最终位于正确的位置（即排序后的最终位置）。
     * 分区过程（关键）：
     * 初始化：left 指针指向数组起始位置，right 指针指向末尾。
     * 从右向左找到第一个小于基准的元素，从左向右找到第一个大于基准的元素。
     * 交换这两个元素，直到 left 和 right 指针相遇。
     * 将基准与相遇点的元素交换，完成分区
     *
     * @param arr  [6, 3, 8, 2, 9, 1]
     * @param low  0
     * @param high arr.length - 1
     * @return
     */
    private static int partition(int[] arr, int low, int high) {
        // 选择第一个元素作为基准
        int pivot = arr[low];
        int left = low;
        int right = high;

        while (left < right) {
            // 从右向左找第一个小于基准的元素
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            // 从左向右找第一个大于基准的元素
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 交换这两个元素
            if (left < right) {
                swap(arr, left, right);
            }
        }
        // 将基准放到正确位置（left 和 right 相遇点）
        swap(arr, low, left);
        // 返回基准的最终位置
        return left;
    }

    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}